package tree;

/**
 * @Description 剑指 Offer 54. 二叉搜索树的第k大节点
 * @Author Firenut
 * @Date 2023-01-24 10:40
 */
public class T54_kthLargest {
    int count;
    int res;

    // 法1:先做一次中序(左根右)，一边存入元素,一边用n值记录元素的个数,然后取索引n-k(但是二叉树结点的个数是不好确定)
    // 法2:中序遍历的逆序是降序排序,使用一个变量count=0,每次遍历让其值+1,知道count==k时返回结点值即可
    // 时间复杂度:O(n) 空间复杂度:O(n)
    public int kthLargest(TreeNode root, int k) {
        inorder(root,k);
        return res;
    }

    void inorder(TreeNode node,int k){
        if(node==null){
            return;
        }
        inorder(node.right,k);//右子树
        this.count++;
        if(count==k){
            this.res=node.val;
            return;
        }
        inorder(node.left,k); //左子树
    }
}